The present invention relates to an electronic payment system in electronic commerce of network, and especially to a system using an unbalanced binary tree structure to calculate. The network used includes an Internet, a telephone network, a dedicated network, a cable TV network, etc.
The basic structure of an electronic payment system 10 is illustrated in FIG. 1. A subscribe computer 1 and a merchant computer 2 perform data communication for completing a transaction through an Internet 3 (or other network). In general, the action of transferring account or verification for security is performed through an electronic payment service center 4 (for example, banks). In FIG. 2, the subscribe computer 1 purchases the total unit n by paying an amount of money to the electronic payment service center 4 and is awarded with an authority. Then, the total unit n is operated by a one-way function h to obtain a contrast data M. If the user desires to consume, the subscribe computer 1 firstly subtracts the unit spent, and uses the current unit k to calculate a value Xk representing current consumption state to the amount of money. These datum (M and Xk) is sent to the merchant computer 2 through the Internet 3. In a reprocessing procedure P, the merchant computer 2 calculates a second value Xxe2x80x2k using identical one-way function h. In the conventional operating process of the subscribe computer 1 with respect to the values M and Xk, a payment chain of one-way hash function shown in FIG. 3 is used, which has the relation of a one-way function Xnxe2x88x921=h(Xn). It means that the value Xn is substituted into a one-way hash function h to operate as a one-dimension function or obtaining the next value Xnxe2x88x921. As shown in this figure, in the subscribe computer 1, starting from substituting the initial value of a random number Xn into an one-way hash function h to perform n times for deriving a contrast data M or to perform nxe2x88x92k times for deriving Xk. Then, in the reprocessing procedure P of the merchant computer 2, by the same one-way hash function h, Xk is operated to generate Xxe2x80x2k and then the value Xxe2x80x2k is contrasted with data M. If Xxe2x80x2k=M, it identifies this transaction is successful, thus the merchant computer 2 provides services or merchandises to the subscriber and requests a transferring account to the electronic payment service center 4, thus storing current Xk as a contrast value M for being used in next consumption.
Since the one-way hash function is irreversible, any Xk only operates in a forward direction (the leftward direction in FIG. 3). Therefore, for each consumption. (with different k value, and value k is increased monotonically to value n), the subscribe computer 1 calculates from Xn to Xk for nxe2x88x92k times. For example, assuming one unit of money is consumed each time, thus, nxe2x88x921 times of function operation are necessary to calculate from Xn to X1. In the next consumption, from Xn to X2 similarly, nxe2x88x922 times of operation are necessary. In further next consumption, from Xn to X3 nxe2x88x923 times of operation is necessary. And for Xnxe2x88x921, only one time of operation from Xn is necessary. Thus, in the conventional calculation, totally, (nxe2x88x921)+(nxe2x88x922)+ . . . +1 times of functional operation are performed, and then this total value is divided by n to obtain an average of       (          n      -      1        )    2
times for each consumption. For such a large amount of operations, the subscribe computer 1 with a finite ability of hardware (for example, an IC card) is insufficient. Therefore, the operation efficiency becomes low. The larger the unit of purchase, the lower the operation efficiency. Thus, the prior art only can be used in an electronic payment system with a smaller amount of money.
Accordingly, the primary object of the present invention is to provide an electronic payment device using an unbalanced binary tree for improving the calculating efficiency of an electronic payment system.
Another object of the present invention is to provide an electronic payment device using an unbalanced binary tree for reducing the operation times of an electronic payment system.
Another object of the present invention is to provide an article of manufacture comprising a medium contained a computer readable program, which can be used in the electronic payment device using an unbalanced binary tree of the present invention for improving the calculating efficiency.
In order to attain the aforementioned objects, in the electronic payment system of the present invention, an operation device is installed in a computer comprising a data providing device for providing datum including the total unit n of the amount of money that user purchases, a first one-way function h1, a second one-way function h2, and the current unit k of the amount of money after current consumption; and a microprocessor. The microprocessor includes a first processing device for selecting two positive integers p and q which conforming the relation pxc3x97q=n; a random number generator for generating a random number and setting the random number as an initial value Xpq; a second processing device to calculate the number a of times of the first one-way function h1 by formula       a    =          q      -              ⌈                  k          p                ⌉              ;
a third processing device to calculate the number b of times of the second one-way function h2 by formula b=[pxe2x88x92(k mod p)] mod p; and a fourth processing device to derive a first data Xk by formula Xk=h2b(h1a(Xpq)). Thereby, the first data Xk of current consumption, or a plurality of contrast values Mq are calculated. After the first data Xk and the contrast values Mq being sent to a merchant computer through a network, the merchant computer performs a reprocess procedure to the first data Xk to form with a second data Xxe2x80x2k, and checking whether the respective contrast value Mq is equal to the second data Xxe2x80x2k, so as to determine whether this transaction is successful.
The data providing device of the present invention is a storing device (such as ROM, hard disk), or an input device (such as a modem) reading data from a network.
It is suggested that the first one-way function h1 and the second one-way function h2 of the present invention are one-way Hash functions, for example, a MD-5 algorithm, a RIPE-MD algorithm, a SHA-1 algorithm, a MDC2 algorithm, or a MDC4 algorithm, etc. It is preferred that the first and second one-way functions h1, h2 are RIPE-MD algorithm, SHA-1 algorithm, respectively. They have the advantages of short data length and preferred reliability.
In the present invention, the operating device can be installed within the subscriber""s computer or the merchant computer. The operating device can be made as an IC card itself (such as a Smart IC card), or the device can be modularized as a chip. Preferably, the procedure of the method of the present invention can be encoded in a medium to serve as a computer readable program to perform the calculation with the unbalanced binary tree. Of course, it can be used in a reprocessing procedure of the merchant computer for reducing operation times and thus improving the operating efficiency.